// 零钱兑换: https://leetcode-cn.com/problems/coin-change/
/*

/*
满足贪心算法，必须具备两点
 1. 每一步都应具有局部最优解
 2. 前面的选择，不会对后面的选择造成影响（无后效性）
*/

package greedy

import "math"

// 贪心 + 回溯， 每次都从最高的开始找， 超过就回溯，找到就停止。
// 但是要记得有种情况： 面值 1 7 10， 找 14. 上面的结果 10 1 1 1 1 五张要大于 7 7 两张！
// 所以只能回溯，穷举所有结果
func coinChange(coins []int, amount int) int {
	coin := make([]int, 0)
	var dfs func(int, []int)
	rst := math.MaxInt32
	dfs = func(total int, coin []int) {
		if total < 0 {
			return
		}

		if total == 0 {
			rst = int(math.Min(float64(rst), float64(len(coin))))
		}

		for _, num := range coins {
			coin = append(coin, num)
			dfs(total-num, coin)
			coin = coin[:len(coin)-1]
		}
	}

	dfs(amount, coin)
	if rst == math.MaxInt32 {
		return -1
	}
	return rst
}
